1. Field of the Invention
The present invention relates generally to computer software. More particularly, the present invention relates to memory management with non-compacting garbage collection.
2. Description of the Relevant Art
The term xe2x80x9cmemory managementxe2x80x9d generally denotes a collection of techniques for providing sufficient memory to one or more processes in a computer system, especially when the system does not have enough memory to satisfy all processes"" requirements simultaneously. Memory management techniques include swapping, paging, virtual memory, and garbage collection. Memory management is usually performed primarily by a hardware memory management unit. Automatic memory management refers to memory management processes which do not require user intervention.
In general, the overheads of automatic memory management can be attributed to allocations of new data structures (e.g., objects), detecting alive (i.e., reachable) objects, disposing of unreachable objects, and memory compaction. Some algorithms do not have all of the above components, and various algorithms differ substantially in the amount of overhead contributed by each of the above-listed components. For example, a mark-and-sweep algorithm may spend a significant amount of time on sweeping memory and merging discovered free blocks into larger contiguous regions, while the main source of overhead of copying-based garbage collection comes from memory compaction. Different algorithms behave differently with respect to space as well; non-copying algorithms typically do not prevent memory fragmentation at all while copying algorithms compact memory to reduce fragmentation.
One of the primary problems encountered in memory management is fragmentation, which is the process or result of splitting a large area of free memory (e.g., on disk or in main memory) into smaller non-contiguous blocks. Fragmentation may occur after many blocks have been allocated and freed. For example, if there are three kilobytes of free space and two 1 k blocks are allocated and then the first one (at the lowest address) is freed, then there will be 2 k of free space split between the two 1 k blocks. The maximum size block that could then be allocated would be 1 k even though there are 2 k free. One solution is to xe2x80x9ccompactxe2x80x9d the free space by moving the allocated blocks to one end (and thus the free space to the other). Fragmentation related to RAM that has small, unused holes scattered throughout it is called external fragmentation. With modern operating systems that use a paging scheme, a more common type of RAM fragmentation is internal fragmentation. Internal fragmentation occurs when memory is allocated in frames, and the frame size is larger than the amount of memory requested.
Garbage collection is the process by which dynamically allocated storage is reclaimed during the execution of a program. The term usually refers to automatic periodic storage reclamation by the garbage collector (usually part of the run-time system), as opposed to explicit code to free specific blocks of memory. Automatic garbage collection is usually triggered during memory allocation when the amount of free memory falls below some threshold or after a certain number of allocations. Normal execution is suspended and the garbage collector is run. There are many variations on this basic scheme. Languages like Lisp represent expressions as graphs built from cells which contain pointers and data. These languages use automatic dynamic storage allocation to build expressions. During the evaluation of an expression it is necessary to reclaim space which is used by sub expressions but which is no longer pointed to by anything. This reclaimed memory is returned to the free memory pool for subsequent reallocation. Without garbage collection the program""s memory requirements would increase monotonically throughout execution, possibly exceeding system limits on virtual memory size. The three main methods are mark-and-sweep garbage collection, reference counting, and copying garbage collection.
In the mark-and-sweep garbage collection scheme, each cell has a bit reserved for marking which is clear initially. During garbage collection, all active cells are traced from the root and marked. Then all cells are examined and unmarked cells are freed.
In the reference counting scheme, each memory cell contains a count of the number of other cells which point to it. If this count reaches zero, the cell is freed and its pointers to other cells are followed to decrement their counts, and so on recursively. This technique cannot cope with circular data structures. Cells in such structures refer (indirectly) to themselves and so will never have a zero reference count. This means they would never be reclaimed, even when there are no references from outside the structure.
In copying-based garbage collection schemes, memory is typically divided into two equal halves, known as the xe2x80x9cfrom spacexe2x80x9d and xe2x80x9cto space.xe2x80x9d Garbage collection copies active cells from the xe2x80x9cfrom spacexe2x80x9d to the xe2x80x9cto spacexe2x80x9d and leaves behind an invisible pointer (an xe2x80x9cindirectionxe2x80x9d) from the old position to the new copy. Once all active cells have been copied in one direction, the spaces are swapped and the process is repeated in the opposite direction. Each time the cells are copied from one space to the other, they are compacted to remove any unused space between them.
A garbage collector must determine which data structures, such as objects, are in use and which are not. A program executing a set of methods may have arguments or local variables that are references to objects. These references are said to belong to a root set of references that are immediately accessible to the program. All objects referenced by this root set of references are said to be reachable by the program in its current state and should not be collected by a garbage collector. Also, those objects might contain references to still other objects, which are also reachable, and so on. All other objects on the heap are considered unreachable, and all unreachable objects are typically eligible for garbage collection and may be reclaimed during garbage collection. Garbage collection algorithms vary, but they typically have in common the task of identifying the objects that are reachable from the root set and reclaiming the space occupied by any other objects. An object may refer to reachable objects and still be unreachable itself. Likewise, an object can be unreachable in spite of references to it, if those references are all from unreachable objects.
Statistical studies show that most objects are small. Many implementations of automatic memory management algorithms take this into account, for instance, by pre-allocating larger chunks of memory and then using them for fast allocation space for small objects. However, fragmentation may still present memory management problems when many of the small objects are allocated and de-allocated during program execution. Memory management approaches to fragmentation which rely upon copying, such as compaction schemes, may require significant overhead, yet the problems associated with memory fragmentation typically require compaction to be solved. Similarly, when many small, short-lived objects are allocated and de-allocated, discovering unreachable objects and making unreachable memory available for allocations may incur large overheads.
Therefore, an improved system and method for memory management are desired.
The problems outlined above are in large part solved by various embodiments of a system and method for memory management. In one embodiment, a memory heap comprises a plurality of memory blocks of a uniform and fixed size. The uniform size of the memory blocks removes the need for variable-size memory block management, which may be substantial in that variable-size memory blocks must have size information associated with them, and the memory manager must read and manage this information. Each memory block in the heap may have associated with it a status bit indicating that block""s current allocation status. In one embodiment, a binary status key stores a Boolean value indicating free memory. Any memory block in the heap whose status bit holds this value is considered to be free for allocation. Memory allocation from the heap may be performed by a memory management program.
In one embodiment, a request may be received for allocation of a quantity of contiguous fixed-size memory blocks, such as to store a data structure or instantiate an object. The heap may be scanned for a contiguous sequence of free fixed-size memory blocks of the requested quantity. The scan may start at a memory block pointed to by a xe2x80x9ccurrentxe2x80x9d pointer, and proceed by examining each sequence of free contiguous memory blocks in order until either a sequence of the requested quantity is found or the end of the heap is reached. As part of the scanning process, the status bit of each scanned free memory block may be set to the logical negative of the binary status key, i.e., marked as un-free. This status bit may become relevant during the garbage collection phase, described below. Any sequence of free blocks which has less than the requested quantity of memory blocks may be skipped but marked as un-free. If the end of the heap is reached before a sequence of sufficient quantity is found and the allocation made, the garbage collection process is executed. This process reclaims unused memory and sets the current pointer at the beginning of the heap, where the scan may then continue.
The garbage collection process sets the status bit for all reachable (e.g., belonging to xe2x80x9calivexe2x80x9d data structures or objects) blocks of memory to the value of the binary status key. This marks all reachable blocks of memory as free. Then, the binary status key is flipped, i.e., set to its logical negative (e.g., non-zero changed to zero, or zero changed to non-zero). This flip provides a new context to all the memory blocks which have been marked during the heap scan. As a result, all memory blocks which were marked free are now considered un-free, while any memory blocks marked as un-free are now considered to be free, or available for allocation. In this manner, any memory block whose corresponding structure or object has become unreferenced (i.e., is not xe2x80x9calivexe2x80x9d) is reclaimed for future use. The current pointer, also referred to as the current block variable, may then be set to the beginning of the heap, from which the heap scan may subsequently continue. Finally, the requested quantity of memory blocks may be allocated from the heap and returned to the calling program.